package meituan;

import com.sun.xml.internal.fastinfoset.tools.XML_SAX_FI;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Map;

/**
 * @author le
 */
public class Meituan5
{
    public static void main(String[] args)
    {
        int[] arr = {1,3,5,2,2};
        int[] res = m_sort(arr);
        for (int i = 0; i < res.length; i++)
        {
            System.out.println(res[i]);
        }

    }

    public static int findKth(int[] a, int n, int K) {
        // write code here
        sort(a,0,a.length-1);
        for (int i = a.length-1; i > 0; i++)
        {
            if (a[i] != a[i-1]){
                K--;
            }
            if (K == 0){
                return a[i];
            }
        }

        return 1;
    }

    public static void sort(int[] arr,int left,int right){
        if (left < right){
            int i = left;
            int j = right;
            int key = arr[left];

            while(i < j){
                while(i < j && arr[j] > key){
                    j--;
                }
                while(i < j){
                    arr[i++] = arr[j];
                }
                while(i < j && arr[i] < key){
                    i++;
                }
                while(i < j){
                    arr[j--] = arr[i];
                }

            }
            arr[i] = key;
            sort(arr,left,i-1);
            sort(arr,i+1,right);
        }
    }


    public static int[] m_sort(int[] source){
        int[] arr = Arrays.copyOf(source, source.length);
        if (arr.length < 2){
            return arr;
        }
        int mid = (int)Math.floor(source.length / 2);
        int[] left = Arrays.copyOfRange(arr,0,mid);
        int[] right = Arrays.copyOfRange(arr,mid,arr.length);


        return merge(m_sort(left), m_sort(right));
    }

    public static int[] merge(int[] left,int[] right){
        int[] res = new int[left.length + right.length];
        int i = 0;
        while(left.length !=0 && right.length != 0){
            if (left[0] > right[0]){
                res[i++] = right[0];
                right =  Arrays.copyOfRange(right,1,right.length);
            }else{
                res[i++] = left[0];
                left = Arrays.copyOfRange(left,1,left.length);
            }
        }

        while(left.length != 0){
            res[i++] = left[0];
            left = Arrays.copyOfRange(left,1,left.length);
        }

        while(right.length != 0){
            res[i++] = right[0];
            right =  Arrays.copyOfRange(right,1,right.length);
        }
        return res;
    }
}
